home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Utilities / Programming / EnterAct 3.5 / Drag_on Modules / hAWK programs / SortLibrary < prev    next >
Encoding:
Text File  |  1991-11-09  |  1.8 KB  |  63 lines  |  [TEXT/KEEN]
  1. #SortLibrary: a heap sort routine. PLEASE NOTE hAWK has a built-in
  2. #“sort” function, this file just demonstrates what a library file
  3. #looks like, and incidentally shows hAWK as an algorithm
  4. #prototyper, using a classic example. If you need to do actual
  5. #sorting, use the built-in “sort” function. See “$WordFrequency”
  6. #for an example of real sorting with hAWK.
  7. #
  8. #“hsort” stands for heap sort, a standard sorting
  9. #method. hsort expects to deal with numeric indexes for the
  10. #array A, starting with 1 rather than 0.
  11. #hsort compares the elements as numbers if both are numbers, otherwise
  12. #it compares them as strings.
  13. #
  14. #If your array is associative, use the following
  15. #approach to sorting it according to the order of the indexes
  16. #(words[] is an array indexed associatively):
  17. #    for (w in words)
  18. #        A[++m] = w SUBSEP words[w]
  19. #    hsort(A, m)
  20. #    for (j = 1; j <= m; ++j)
  21. #        {
  22. #        A[j] = substr(A[j], index(A[j], SUBSEP) + 1)
  23. #        print A[j]
  24. #        }
  25. #What we did there was: tack the index itself onto the beginning of
  26. #each array element, and load this element into a numerically–indexed
  27. #array; sort the new array; then loop over the new array in numeric
  28. #order, stripping off the index before printing.
  29. #To sort an associative array by the value of its elements rather than
  30. #its indexes, proceeed as above but don't tack the index onto the
  31. #front of each element of A[], ie use
  32. #    for (w in words)
  33. #        A[++m] = words[w]
  34. #as the first step.
  35. #
  36.  
  37. function hsort(A,n,        i)
  38.     {
  39.     for (i = int(n/2); i >= 1; i--)
  40.         heapify(A,i,n)
  41.     for (i = n; i> 1; i--)
  42.         {
  43.         swap(A,1,i)
  44.         heapify(A,1,i-1)
  45.         }
  46.     }
  47.  
  48. function heapify(A,left,right,        p,c)
  49.     {
  50.     for (p = left; (c = 2*p) <= right; p = c)
  51.         {
  52.         if (c < right && A[c+1] > A[c])
  53.             c++
  54.         if (A[p] < A[c])
  55.             swap(A,c,p)
  56.         }
  57.     }
  58.  
  59. function swap(A,i,j,        t)
  60.     {
  61.     t = A[i]; A[i] = A[j]; A[j] = t
  62.     }
  63.